1. Field of the Invention
The present invention relates to network communication systems, and in particular to packet scheduling.
2. Description of the Related Art
Network applications, such as video-conferencing and multimedia broadcasts, place large amounts of data on a network, thereby causing contention for network resources. Conventionally, such applications rely on packet scheduling algorithms in gateways to enhance performance and provide an acceptable level of quality of service. A packet scheduler controls the allocation of network interface bandwidth with respect to outgoing network flows, by deciding which packet is sent at a given time. In so doing, a packet scheduler determines how bandwidth is shared among flows and plays a key role in determining the rate and timing behavior of the transmission of data. A desirable and important property of a packet scheduler is the fairness it achieves in the allocation of the bandwidth resources on the output flow. The most commonly used notion of fairness is that no flow should receive more service than it demands and that no flow with an unsatisfied demand should receive less service than any other flow. The well known Generalized Processor Sharing (GPS) scheduler, described in A. Parekh and R. Gallager, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Network,” IEEE Transactions on Networking,” vol. 1, no. 3, June 1993, purports to provide an ideally fair scheduling algorithm. However, while GPS may provide an ideal method for best-effort and interactive connections in a theoretical sense, it is impossible to implement due to its requirement of infinitesimal sized packets. It is not, therefore, a practical solution.
Practical packet schedulers can be classified broadly as either timestamp schedulers or round-robin schedulers. Timestamp schedulers attempt to emulate the operation of GPS by computing a timestamp for each packet. Packets are then transmitted in increasing order of their timestamps. Well-known examples of timestamp scheduling algorithms were introduced by J. Bennet and H. Zhange, in “WF2Q: Worst case fair weighted fair queuing,” IEEE INFOCOM '96 (1996); N. Figueira and J. Pasquale, in “Leave-in-time: A new service discipline for real-time communications in a packet-switching network,” ACM SIGCOMM '95 (1995) and A. Demers, S. Keshav and S. Shenker, in “Analysis and simulation of a fair queuing algorithm,” Internet Res. and Exper., vol. 1, 1990. In general, although timestamp schedulers have good delay properties, they suffer from a sorting bottleneck that results in time complexities (i.e., work) of O(N) to O(log N), where N is the number of competing flows. In addition, the implementation of timestamp schedulers requires a complicated data structure that typically is not well suited for hardware implementation.
Round-robin schedulers are the other broad class of packet schedulers. These schedulers typically assign time slots to flows in a round-robin fashion. By eliminating the sorting bottleneck associated with timestamp schedulers, they can achieve a O(1) time complexity. Deficit Round Robin (DRR) is a well-known example of a round-robin scheme. DRR is described in M. Shreedhar and G. Varghese, “Efficient Fair Queuing using Deficit Round Robin,” ACM SIGCOMM, August 1995, incorporated herein by reference. In DRR, each flow is assigned a quantum that is proportional to the weight of the flow. Packets are transmitted in rounds, where a targeted amount of data of a flow to be transmitted in each round is the quantum of the flow. Due to the granularity of packet size, the amount of data transmitted in a round may not be exactly equal to the quantum. A deficit counter is associated with each flow to record the unused quantum. This allows the unused quantum to be passed to the next round. Once a flow is serviced, it will wait until next round to transmit data. Since all data of a flow to be transmitted in a round is transmitted at once, DRR has poor delay and burstiness properties, especially for flows with large weights.
The Smoothed Round Robin (SRR) scheme described in Guo Chuanxiong, “SRR: An O(1) Time Complexity Packet Scheduler for Flows in Multi-Service Packet Networks,” Proc. SIGCOMM 2001, incorporated herein by reference, improves the delay and burstiness problems by spreading the data of a flow to be transmitted in a round over the entire round using a specially designed sequence that can distribute output traffic of each flow evenly. SRR has short-term fairness and certain schedule delay bound, as well as O(1) time complexity. A Weight Spread Sequence (WSS) and a Weight Matrix are used as two key data structures of the scheduler. WSS is a specially designed sequence that can distribute the output traffic of each flow evenly. SRR codes the weights of the flows into binary vectors to form a Weight Matrix, and then uses the corresponding WSS to scan the Weight Matrix. Although SRR results in better delay bounds than DRR, the worst case delay experienced by a packet is still proportional to N, the number of flows. In addition, SRR, like timestamp scheduling, is not simple to implement.
Plainly, the prior art scheduling techniques have significant drawbacks, and can often result in large queuing delays during busy periods. Even with the large buffers provided in today's gateway products, queues can become congested. During congestion periods, the buffers may become and remain close to full, subjecting packets to long delays, even when the intrinsic latency of a communications path is relatively small. Even worse, packets might be dropped.
Accordingly, there is a need for an improved packet scheduler which achieves fair allocation of the bandwidth resources on the output link, reduces congestion and lowers packet losses. There also is a need for a packet scheduler that has low complexity and is amenable to a simple hardware implementation.